Abstract

我是阿傑，由於 sort() 這個咩色的 ECMAScript 的演算法非常複雜，為了避免文章過於龐大，會將其拆成 2 天介紹：

第 1 天 (Day 28)：

• 使用時機
• 語法
• 說明
• 範例
• 注意事項

第 2 天 (Day 29)

• ECMAScript
• 結論

sort() 這個 method 的全寫應該是 Array.prototype.sort，有興趣可以看 Day 2 的介紹，這邊會直接使用 sort() 作為替代。

範例的 callback 都會使用箭頭函式做介紹，如果尚不熟悉的話可以參考 MDN 的介紹。

最後會透過分析 ECMAScript 來驗證是否有吻合，如果覺得 ECMAScript 有點艱澀難懂，我們在 Day 4 、Day 5 有介紹其相關術語可以幫助閱讀。

使用時機

當你想要對一個陣列重新排序時，sort() 會直接變動原陣列的順序。

你可以選擇是否要使用預設的排序方式 (利用字典序排序)，或者提供一個 compareFn 參數來自定義排序的方式。

語法

直接呼叫 (不帶入 compareFn)

sort()

Arrow function (直接定義箭頭函式)

sort((a, b) => { /* ... */ })

callback (直接傳入回呼函式)

sort(compareFn)

Inline Callback (直接定義匿名函式)

sort(function(a, b) {
	/* ... */
})

參數

sort() 可以帶入一個可選的 compareFn 參數。

compareFn (可選的)

這個函式可以用來決定排序的順序，又被稱為 comparator。

如果沒有提供 comparator，sort() 會根據每個字元 (character) 的 UTF-16 編碼來進行排序。

這個 compareFn 每次呼叫時會被傳入 2 個參數 a、b，分別代表著 2 個要被比較的元素，這也表示我們的 compareFn 需要定義對應的 2 個參數：

• a - 用來比較的第 1 個元素
• b - 用來比較的第 2 個元素

Return Value

會回傳原陣列的參照 (reference)。

要注意原陣列已經被重新排序過。

Mutability

會改動到原陣列。

說明

有沒有提供 compareFn 參數會影響 sort() 的行為：

• 未提供自定義的 compareFn 時，會使用預設的 comparator，這是一種字典序 (lexicographic) 的排序方法，它會將陣列的每個元素轉成字串，並利用它們的 UTF-16 編碼來進行比較，最後以升冪 (ascending) 的結果呈現，可以想像先使用 join() 將陣列轉換成字串再進行排序，例如以下：

const array = ['Russ', 5, '80', 'Emma', '100']
console.log(array.join())
// 'Russ,5,80,Emma,100'

• 如果提供了 compareFn，所有不是 nudefined 的元素都會根據 cmpareFn 回傳的值來排序，而所有的 undefined 元素都會被排在陣列的最末端，且不會被帶入 compareFn 來呼叫。

sort() 會根據 compareFn 回傳的值來決定元素如何排序，可參考這張表格：

我們可以根據上面這張表格來設計我們的 compareFn：

function compareFn(a, b) {
	if ('依據特定的排序標準，a 小於 b 時') return -1;

	if ('依據特定的排序標準, a 大於 b 時') return 1;

	// a 等同於 b
	return 0
}

如果我們想要對數字做排序 ，我們可以讓 compareFn(a, b) 的 a、b 參數相減，例如以下的範例會讓陣列升冪 (ascending) 排列：

function comparator(a, b) {
	return a - b
}

而這樣則可以讓陣列降冪 (descending) 排列：

function comparator(a, b) {
	return b - a
}

排序的演算法種類非常繁多，ECMAScript 並沒有要求實作必須使用哪些演算法，但從 ES 10 開始便規定其排序結果都必須為穩定的 (stable)，這也表示實作上必須使用穩定的排序演算法，也就意味著不會再出現非預期的結果，因此我們只需要專注在排序的使用，不需要額外花太多心思在底層的排序演算法上(關於穩定性可以參考 Wiki 的說明)。

sort() 會保留稀疏陣列的 empty slot，這些 empty slot 會被移動到陣列的最後方，而且永遠會排在 undefined 之後，可參考範例的 Example - 4。

範例

Example 1 - 未提供 compareFn (預設的排序方法)

const names = ['Russ', 'Emma', 'Brando', 'Alejo']
console.log(names.sort())
// ['Alejo', 'Brando', 'Emma', 'Russ']

const numbers = [2, 48, 10, 5, 1000]
console.log(numbers.sort())
// 預期排序: [2, 5, 10, 48, 1000]
// 實際排序： [10, 1000, 2, 48, 5]

const mixed = ['Russ', 20, '6', 'Alejo']
console.log(mixed.sort())
// [20, '6', 'Alejo', 'Russ']

如果不提供 compareFn 的話， sort() 會使用預設的排序方法，可以發現在字串的排序不會有問題，但使用在數字的排序就會產生跟預期不一樣的結果， 例如 numbers 的排序。

Example 2 - 提供自定義的 cmpareFn

const names = ['Russ', 'Emma', 'Brando', 'Alejo']
console.log(names.sort(comparator))
// ['Russ', 'Emma', 'Brando', 'Alejo']

const numbers = [2, 48, 10, 5, 1000]
console.log(numbers.sort(comparator))
// [2, 5, 10, 48, 1000]

const mixed = ['Russ', 20, '6', 'Alejo']
console.log(mixed.sort(comparator))
// ['Russ', '6', 20, 'Alejo']

function comparator(a, b) {
	return a - b
}

可以看到這個自定義的 comparator 無法對字串進行排序， 但可以對數字進行升冪排序。

Example 3 - 排序物件陣列

const profiles = [
	{ name: 'Emma', age: 25 },
	{ name: 'Russ', age: 18 },
	{ name: 'Damien', age: 48 },
	{ name: 'Cate', age: 33 },
	{ name: 'Alejo', age: 30 }
]

const sortedByAge = [...profiles].sort((a, b) => a.age - b.age)
console.log(sortedByAge)
/*
[
	{name: 'Russ', age: 18},
	{name: 'Emma', age: 25},
	{name: 'Alejo', age: 30},
	{name: 'Cate', age: 33},
	{name: 'Damien', age: 48}
]
*/

const sortedByName = [...profiles].sort((a, b) => {
	const nameA  = a.name.toLowerCase()
	const nameB  = b.name.toLowerCase()
	// 忽略大小寫

	if (nameA < nameB) return -1
	
	if (nameA > nameB) return 1

	return 0
})

console.log(sortedByName)
/*
[
	{name: 'Alejo', age: 30},
	{name: 'Cate', age: 33},
	{name: 'Damien', age: 48},
	{name: 'Emma', age: 25},
	{name: 'Russ', age: 18}
]
*/

這裡在對 age 跟 name 做排序時，分別使用了不同的 comparator，以達到對字串跟數字的預期排序。

Example 4 - 當陣列為稀疏陣列且有 undefined 元素

const array = ['c', , 'b', undefined, 'a']


console.log(array.concat().sort())
// ['a', 'b', 'c', undefined, empty]

console.log(array.concat().sort(comparator))
// ['a', 'b', 'c', undefined, empty]

function comparator(a, b) {
	if (a < b) return -1

	if (a > b) return 1

	return 0
}

在這裡可以看到不論是否使用預設的排序方式，undefined 跟 empty slot 都會被排到陣列的最後方，而 empty slot 則永遠會再 undefined 之後。

注意事項

comparator 應該要具有以下特點，這樣才能確保 sort() 在排序時不會出現非預期的錯誤：

• Pure - comparator 不應該改動到原陣列或任何外部的狀態，因為我們無法得知 comparator 會被 sort() 如何呼叫、呼叫幾次！所以它不應該產生任何對於外部的副作用；因此更改陣列元素這件事還是交給 sort() 本身即可，這也是避免產生一些高併發的結果 (concurrency)。
• Stable - 當輸入相同的配對 (pair) 應該都要回傳相同的結果。
• Reflexive - 元素自身的比較應該要相同且回傳 0，例如 compareFn(a, a) === 0。
• Symmetric - 2 個元素互換其回傳的結果應都為 0，或者為相同的值加上負值符號 (opposite sign) ，例如 1 跟 -1。
• Transitive - 如果 compareFn(a, b) 跟 compareFn(b, c) 的結果都為正數，那 compareFn(a, c) 的結果也應該為正數，也就是說如果 b 大於 a， c 大於 b， 那 c 也應該大於 a。

而 sort() 預設的 comparator 便符合上述的所有特性。

由於 ECMAScript 並沒有規定實作所應使用的演算法，因此 sort() 實際的效能（時間、空間複雜度) 完全取決於實作上真正選擇的演算法，我們無法直接從規範得知最後的實際結果，例如 V8 目前使用的為 Tim Sort 演算法，而非以前的 Quick Sort + Insertion Sort，因此最終排序的效能結果也會不同。

sort() 預設使用字典序 (lexicographic) 的排序方式，也就是會使用它們的 UTF-16 編碼來進行比較，如果想知道確切的編碼，可以使用 chartCodeAt() 之類的 String method 來自行查看。

在 ECMAScript 的第 10 版 (ECMAScript 2019)， 規範便要求 sort() 必須是穩定的 (stable)，我們來驗證一下 (不穩定的情形可能會發生在 10 筆以上， 可以自行試驗看看)：

const profiles = [
	{ name: 'Emma', age: 18 },
	{ name: 'Russ', age: 33 },
	{ name: 'Damien', age: 18 },
	{ name: 'Cate', age: 25 },
]

profiles.sort((a, b) => a.age - b.age)

console.log(profiles)
/*
[
	{name: 'Emma', age: 18},
	{name: 'Damien', age: 18},
	{name: 'Cate', age: 25},
	{name: 'Russ', age: 33}
]
*/

上述的結果為穩定的 - Emma 物件仍排在 Damien 物件之前。

在第 10 版之前，實作上的 sort() 可能會根據陣列長度而使用不同的演算法，通常較長的陣列為了效能上的考量，所選擇的演算法會產生不穩定的排序結果，而這個結果對還不熟悉 JavaScript 的開發者來說非常地迷惑！因此 ECMAScript 便在第 10 版加入了 sort() 必須是穩定的這個規定 (不論陣列長短)，而這個提案便是由鼎鼎大名的 V8 所提出，想知道詳細的前因後果可以參考它們的文章：

• Stable Array.prototype.sort - V8

sort() 被刻意做成通用的，它也可以使用在除了陣列以外的物件上，但這個物件必須包含 length 屬性及整數鍵值 (key) 的屬性，例如以下：

const fakeArray = {
	0: 2,
	1: 3,
	2: 0,
	length: 3
}

console.log([].sort.call(fakeArray))
// {0: 0, 1: 2, 2: 3, length: 3}

由於 sort() 會直接變動到原陣列，如果想要維持 Immutable 的原則，可以儘量先淺拷貝 ( shallow copy) 原陣列再進行排序，例如：

const array = [2, 1, 0, 5, 3]
const sorted = array.concat().sort()

console.log(sorted)
// [0, 1, 2, 3, 5]
console.log(array)
// [2, 1, 0, 5, 3]

小結

由於 sort() 的篇幅較為龐大，所以這邊將 ECMAScript 的部分獨立出來，我們會於明天 (Day 29) 做介紹，虱目魚 Die 吧！

最後，希望大家可以開心地使用各種咩色，體驗它帶給你的便利，祝大家歸剛沒煩惱。

參考資源

• Array.prototype.sort - MDN
• Draft ECMA 262 - TC39